The increasing mobility of users and growing use of a variety of computing devices has motivated widespread interest in secure roaming. Of particular importance is the ability of users to leverage short keys or other “weak” passwords to achieve secure functionality in conjunction with trusted servers. A very common aim of the roaming user is to download credentials from a trusted server onto a “lightweight” device, i.e., a device having limited processing power, memory or other computational resources. Such devices include, by way of example, mobile telephones, personal digital assistants (PDAs), game consoles, etc. Users of such devices may alternatively seek to delegate to the trusted server any cryptographic operations requiring intensive computing or careful key storage, such as digital signing and public-key-based decryption. Another important need for roaming users is that of password recovery or reset.
The roaming user may employ any of a number of different devices, not all of which necessarily possess the same software or configuration. While smart cards and similar key-storage devices offer a harmonized approach to security for the mobile user, they lack an adequately developed supporting infrastructure. At present, for example, very few computing devices contain smart card readers, particularly in the United States. Furthermore, many users find physical authentication tokens inconvenient. It also may be necessary to authenticate roaming users who have lost or forgotten their tokens. Today, this is commonly achieved by asking users to provide answers to a set of “life questions,” i.e., questions regarding personal or private information. These observations stress the need to enable roaming users to employ short pieces of memorable information or other weak passwords as a form of authentication.
In many basic roaming protocols, passwords are stored in a central database, and consequently are vulnerable to theft en bloc in the event of server compromise. Such protocols are often based on secure password-authenticated key agreement (SPAKA). In a typical SPAKA protocol implementation, a client and server share a password, which is used to achieve mutual assurance that a cryptographically strong session key is shared privately by the two parties. To address the problem of weak passwords, SPAKA protocols are constructed so as to leak no password information, even in the presence of an active attacker. When used as a means of authentication to obtain credentials from a trusted server, a SPAKA protocol is typically supplemented with a throttling or lockout mechanism to prevent on-line guessing attacks. Many roaming-credentials proposals involve use of a SPAKA protocol as a leverage point for obtaining credentials, or as a freestanding authentication protocol.
As indicated above, however, the design of most SPAKA protocols overlooks the fundamental problem that the server itself represents a serious vulnerability. As SPAKA protocols require the verifying server to have plaintext access to user passwords or to derivative material, compromise of the server leads potentially to exposure of the full database of passwords. While many SPAKA protocols store passwords in combination with so-called “salt” or in an exponentiated form, an attacker still has the possibility of mounting off-line dictionary attacks. Additionally, these systems offer no resistance to server corruption. An attacker that gains control of the authenticating server can spoof successful login attempts.
To address the above-noted problems with conventional SPAKA-based techniques, Ford and Kaliski have proposed a collection of password “hardening” schemes involving multiple servers, with password privacy assured in the case that at least some servers remain uncompromised. See W. Ford and B. S. Kaliski Jr., “Server-Assisted Generation of a Strong Secret from a Password,” Proceedings of the IEEE 9th International Workshop on Enabling Technologies (WETICE), NIST, Gaithersburg Md., June 2000, which is incorporated by reference herein. In their system, a client parlays a weak password into a strong one through interaction with one or multiple hardening servers, each one of which blindly transforms the password using a server secret.
As a more particular example, the client in one version of the Ford and Kaliski system obtains what may be regarded as a blind function evaluation σi or “share” on its password P from each hardening server Si. The function in question is based on a secret unique to each server and user account. The client combines the set of shares {σi} into a single secret σ, which serves as a strong key that the user may then use in secure authentication applications, e.g., to decrypt credentials, to authenticate himself or herself, etc. Given an appropriate choice of blind function evaluation scheme, servers in this protocol may learn no information, in an information-theoretic sense, about the password P.
The Ford and Kaliski system has been extended to a threshold setting, leading to more complex protocols, but with rigorous security assurances in a broadly inclusive attack model, in P. Mackenzie et al., “Threshold Password-Authenticated Key Exchange,” Research Papers on Strong Password Authentication, http://www.integritysciences.com/links.html, 2002, which is incorporated by reference herein. In particular, P. Mackenzie et al. demonstrate a protocol such that a client communicating with any k out of n servers can establish session keys with each of the k servers by means of password-based authentication, such that even if k−1 servers conspire, the password of the client remains private. Their system can be straightforwardly leveraged to achieve secure downloadable credentials.
The Mackenzie et al. system, however, imposes considerable overhead of several types. First, servers must possess a shared global key and local keys as well, for a total of 4n+1 public keys. The client, additionally, must store n+1 certified public keys. The client must perform several modular exponentiations per server for each session initiation, while the computational load on the servers is high as well. Finally, the Mackenzie et al. protocol is rather complex, both conceptually and in terms of implementation. On the other hand, the Mackenzie et al. protocol is apparently the first such protocol provided with a rigorous proof of security under the Decision Diffie-Hellman assumption in the random oracle model.
Despite their advantages, the known techniques described above have not fully satisfied the security needs of roaming users, particularly with regard to permitting those users to authenticate themselves in a secure and efficient manner using weak passwords communicated via lightweight devices.